Perturbations targeting the graph structure have proven to be extremely effective in reducing the performance of Graph Neural Networks (GNNs), and traditional defenses such as adversarial training do not seem to be able to improve robustness. This work is motivated by the observation that adversarially injected edges effectively can be viewed as additional samples to a node's neighborhood aggregation function, which results in distorted aggregations accumulating over the layers. Conventional GNN aggregation functions, such as a sum or mean, can be distorted arbitrarily by a single outlier. We propose a robust aggregation function motivated by the field of robust statistics. Our approach exhibits the largest possible breakdown point of 0.5, which means that the bias of the aggregation is bounded as long as the fraction of adversarial edges of a node is less than 50%. Our novel aggregation function, Soft Medoid, is a fully differentiable generalization of the Medoid and therefore lends itself well for end-to-end deep learning. Equipping a GNN with our aggregation improves the robustness with respect to structure perturbations on Cora ML by a factor of 3 (and 5.5 on Citeseer) and by a factor of 8 for low-degree nodes.

The time cost of the proposed aggregation function in practice is not given, though the worse case complexity is somehow analyzed, but practitioners may care more about the time, i.e., what's the time cost to finish one epoch training/(or one inference) compared to the time of vanilla models like GCN? also what's the time cost compare to other defense? In line 158, it's mentioned that soft medoid comes with the risk of a higher bias for small perturbations and high epsilon, the author should take this effect into account when conducting experiments, to better show the shortcomings out to readers. As found in the paper, this increased robustness against structure-based attacks comes with a cost of decreasing robustness on attribute attacks, the author should make it clear how much robustness lost to attribute attacks by using soft medoid aggregation, otherwise, the method just makes the model robust to structure attacks but super vulnerable to attribute inference attacks.

This paper proposed a new robust aggregation function for graph neural networks to defend against adversarial attacks. The questions raised by the reviewers have been addressed properly in the rebuttal. However, one of the reviewers found that the theoretical analysis provided in this paper does not really prove the "adversarial robustness" of the proposed aggregation function. More specifically, the analysis only shows that an attacker is harder to turn the aggregated results into -\infty, while for adversarial robustness it is necessary to show "the aggregated results won't change significantly with small input perturbation". AC and other reviewers agree with this point but think this paper still has enough novelty and empirical contributions.

Perturbations targeting the graph structure have proven to be extremely effective in reducing the performance of Graph Neural Networks (GNNs), and traditional defenses such as adversarial training do not seem to be able to improve robustness. This work is motivated by the observation that adversarially injected edges effectively can be viewed as additional samples to a node's neighborhood aggregation function, which results in distorted aggregations accumulating over the layers. Conventional GNN aggregation functions, such as a sum or mean, can be distorted arbitrarily by a single outlier. We propose a robust aggregation function motivated by the field of robust statistics. Our approach exhibits the largest possible breakdown point of 0.5, which means that the bias of the aggregation is bounded as long as the fraction of adversarial edges of a node is less than 50%.